MPRI 1.24 - Randomized Algorithms - Nicolas Schabanel <br /> <br />Lecture 4 (Part B/C) Thursday Feb 13, 8:45-11:45 - Expander graphs <br />• Expansion: Combinatoric definition <br />• Expansion: Spectral definition <br />• Cheeger inequalities and first applications <br />• Expander constructions: Examples and Zig-Zag product <br /> <br />Exercise session 4: <br />• Zig-zag product <br />• Graph constraints satisfaction Gap-problem: Degree uniformization step <br />• Random walks on expanders are almost sequences of independent trials
